package uk.org.landeg.euler.problems;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;

import junit.framework.Assert;

import org.junit.Test;

import uk.org.landeg.euler.PrimeGen;
import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;
import uk.org.landeg.euler.problems.lib.NumbersLib;

public class Problem060 extends AbstractProblem{
	long[] primes;
	ArrayList<Long> solution;
	int primeSearchRange[];
	long p[] = new long[5];
	int it[] = new int[5];
	ArrayList<long[]> candidateSolutions;

	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem060());
		launcher.solve();		
	}

	int lowestSum = Integer.MAX_VALUE;
	ArrayList<Long> lowestSet;
	
	private boolean minSumExceeded () {
		return (getSolutionSum() > lowestSum); 
	}
	
	private int getSolutionSum () {
		long sum = 0;
		for (Long i : solution) {
			sum += i;
		}
		return (int)sum;
	}

	private void checkLowestSet(ArrayList<Long> solution) {
		int sum = 0;
		for (Long l : solution) {
			sum+= l;
		}
		if (sum < lowestSum) {
			lowestSet = new ArrayList<Long>();
			lowestSet.addAll(solution);
			lowestSum = sum;
		}
	}


	public Object solve () {
		PrimeGen.generate(50000);
		ArrayList<Long> tmpPrimes = new ArrayList<Long>();
		tmpPrimes.addAll(PrimeGen.getPrimes());
		System.out.println("Generated " + tmpPrimes.size() + " primes");
		
		primes = new long[tmpPrimes.size()];
		int id = 0;
		for (long p : tmpPrimes) {
			primes[id++] = p;
		}
		long minSum = Integer.MAX_VALUE;
		long p1,p2,p3,p4,p5;
		int id1, id2, id3, id4, id5;
		for (id1 = 0 ;id1 < primes.length ; id1++) {
			p1 = primes[id1];
			if (p1 > 30) {
				return 0;
			}
			for (id2 = id1 + 1 ;id2 < primes.length ; id2++) {
				p2 = primes[id2];
				if (concatsToPrime(p2, p1)) {
					for (id3 = id2 + 1 ;id3 < primes.length ; id3++) {
						p3 = primes[id3];
						if (concatsToPrime(p3, p1) && concatsToPrime(p3, p2)) {
							for (id4 = id3 + 1 ;id4 < primes.length ; id4++) {
								p4 = primes[id4];
								if (concatsToPrime(p4, p1) && concatsToPrime(p4, p2) && concatsToPrime(p4, p3)) {
									for (id5 = id4 + 1 ;id5 < primes.length ; id5++) {
										p5 = primes[id5];
										if (concatsToPrime(p5, p1) && concatsToPrime(p5, p2) && concatsToPrime(p5, p3) && concatsToPrime(p5, p4)) {
											long sum = p1 + p2 + p3 + p4 + p5;
											minSum = (sum < minSum) ? sum : minSum;
											System.out.println(String.format("%d %d %d %d %d : %d", p1,p2,p3,p4,p5,minSum));
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return null;
	}
	
	protected void injectPrime (final int location, int primeId, final long originalSolution[]) {
		long solution[] = Arrays.copyOf(originalSolution, 5);
		
		if (location == 5) {
			System.out.println(Arrays.toString(solution));
			candidateSolutions.add(solution);
			return;
		}
		long thisPrime;
		boolean concats;
//		for (int idx = 0 ; idx< 20 ; idx++) {
		for (int idx = primeId+1 ; idx < primes.length ; idx++) {
//			System.out.println(Arrays.toString(solution));
			concats = true;
			thisPrime = primes[idx];
			if (location == 0) {
				System.out.println(thisPrime);
				solution[0] = 0;
			}
			concats = true;
			for (long test : solution) {
				if (test == 0) {
					break;
				}
				if (test > 0 && !concatsToPrime(thisPrime, test)) {
					concats = false;
					break;
				}
			}
			if (concats) {
				if (location == 0) {
					if (thisPrime > 50) {
						return;
					}
					System.out.println(thisPrime);
				}
				solution[location] = thisPrime;
				injectPrime(location+1, idx,solution);
			}
		}
	}
	
//	protected void appendPrime (ArrayList<Long> solution, int maxId) {
//		return null;
//	}
	BigInteger val1,val2;
	long concat;
	protected boolean concatsToPrime (long n1, long n2) {
		concat = (NumbersLib.concat(n1, n2));
		if (NumbersLib.sumDigits(concat) % 3 == 0) {
			return false;
		}
		if (!PrimeGen.isPrimeFast(concat, 15)) {
			return false;
		}
		concat = (NumbersLib.concat(n2, n1));
		return PrimeGen.isPrimeFast(concat, 15);
	}
	
	@Test
	public void testConcatsToPrime () {
		Assert.assertTrue(concatsToPrime(1L,3L));
		Assert.assertFalse(concatsToPrime(5L,7L));
	}
	
	protected boolean concatsToPrime (Long... primes) {
		for (int i = 0 ; i < primes.length ; i++) {
			for (int j = 0 ; j < primes.length ; j++) {
				if (i != j) {
					if (!PrimeGen.isPrime(NumbersLib.concat(primes[i], primes[j]))) {
						return false;
					}
				}
			}
		}
		return true;
	}

	@Override
	public String getDescription() {
		// TODO Auto-generated method stub
		return "Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime";
	}
	@Override
	public Integer getProblemNumber() {
		// TODO Auto-generated method stub
		return 60;
	}
}
